package dynamic.dpPack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 多重背包
 */
public class MultiplePack {

    private int packMultipleDp(int V, int[] c, int[] w, int[] n) {
        int[] dp = new int[V+1];
        for (int i=1; i<=c.length; i++) {
            for (int j=V; j>=c[i-1]; j--) {  //----------------为什么倒序?
                for (int k=0; k<=n[i-1] && k*c[i-1]<=j; k++) {
                    dp[j] = Math.max(dp[j], dp[j-k*c[i-1]]+k*w[i-1]);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[V];  //--------------------为甚么是dp[V]?
    }

    // 二进制分解
    private int packMultipleDpBinary(int V, int[] c, int[] w, int[] n) {
        int[] dp = new int[V+1];
        List<Good> goods = new ArrayList<>();
        // 全部数据更改为01背包问题
        for (int i=1; i<=c.length; i++) {
            int k;
            for (k=1; k<=n[i-1]; k<<=1) {
                goods.add(new Good(k*c[i-1], k*w[i-1]));
            }
            if (n[i-1] - k>>1 > 0) {
                goods.add(new Good((n[i-1] - k>>1)*c[i-1], (n[i-1] - k>>1)*w[i-1]));
            }
        }
        // 使用01背包解决问题
        for (Good good: goods) {
            for (int j=V; j>=good.getC(); j--) {
                dp[j] = Math.max(dp[j], dp[j-good.getC()]+good.getW());
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[V];
    }

    class Good {
        private int c;
        private int w;

        Good(int c, int w) {
            this.c = c;
            this.w = w;
        }

        public int getC() {
            return c;
        }

        public void setC(int c) {
            this.c = c;
        }

        public int getW() {
            return w;
        }

        public void setW(int w) {
            this.w = w;
        }
    }

    // O(VN)解法 单调队列

    public static void main(String[] args) {
        int[] c = new int[]{2, 3, 4, 5, 1};  // 费用/重量
        int[] w = new int[]{6, 5, 4, 3, 2};  // 价值
        int[] n = new int[]{1, 2, 2, 2, 2};  // 数量
        int V = 4;  // 背包容量
        MultiplePack multiplePack = new MultiplePack();

        int ans1 = multiplePack.packMultipleDp(V, c, w, n);
        System.out.println("dp ans1:"+ans1);

        int ans2 = multiplePack.packMultipleDpBinary(V, c, w, n);
        System.out.println("dp ans2 binary:"+ans2);
    }
}
